package algorithm
{
	import flash.utils.Dictionary;
	
	import struct.OrderedList;

	public class DijkstraForMap
	{
		private var _passable:IPassable;
		private var _open:OrderedList;
		private var _step:int;
		private var _close:Dictionary;
		private var _nodeIndex:Dictionary;
		private var _edges:Array = [[1, 0], [-1, 0], [0, 1], [0, -1]];
		
		public var xMax:int;
		public var yMax:int;
		
		public function DijkstraForMap(passable:IPassable, xMax:int, yMax:int)
		{
			_passable = passable;
			this.xMax = xMax;
			this.yMax = yMax;
		}
		
		public function solve(fromX:int, fromY:int, step:int):Dictionary {
			_open = new OrderedList;
			_close = new Dictionary();
			_nodeIndex = new Dictionary();
			_step = step;
			var node:DijkstraVertex = getNode(fromX, fromY);
			node.G = 0;
			_open.add(node);
			var p:DijkstraVertex;
			while (_open.count > 0) {
				p = _open.unshift() as DijkstraVertex;
				for each (var offset:Array in _edges) {
					calculateDistance(p, p.x+offset[0], p.y+offset[1]);
				}
				addToS(p);
				trace("===========================");
				_open.print();
			}
			return _close;
		}
		
		public function addToS(node:DijkstraVertex):void {
			_close[node] = node;			
		}
		
		public function isInClose(node:DijkstraVertex):Boolean {
			return _close[node] != null;
		}
		
		public function getNode(x:int, y:int):DijkstraVertex {
			var node:DijkstraVertex = findFromIndex(x, y);
			if (node == null) {
				node = new DijkstraVertex(x, y, int.MAX_VALUE);
				node.G = int.MAX_VALUE;
				node.H = int.MAX_VALUE;
				addToIndex(node);
			}
			return node;
		}
		
		public function addToIndex(node:DijkstraVertex):void {
			_nodeIndex[key(node.x, node.y)] = node;
		}
		
		public function findFromIndex(x:int, y:int):DijkstraVertex {
			return _nodeIndex[key(x, y)];
		}
		
		public function key(x:int, y:int):Object {
			return x + y * xMax;
		}
		
		public function getH(node:DijkstraVertex, pre:DijkstraVertex):Number {
			var result:int = 0;
			if (pre.pre != null) {
				if ((pre.pre.x-pre.x) * (pre.y-node.y) != (pre.x-node.x) * (pre.pre.y-pre.y)) {
					result += 1;
				}
			}
			return result;
		}
		
		public function calculateDistance(pre:DijkstraVertex, x:int, y:int):void {
			if (!_passable.passable(x, y)) return;
			var node:DijkstraVertex = getNode(x, y);
			if (isInClose(node)) return;
			if (node.G + node.H > pre.G + 1 + getH(node, pre)) {
				node.G = pre.G +1;
				node.H = getH(node, pre);
				node.pre = pre;				
				if (node.G <= _step) {
					if (_open.hasContent(node)) {
						_open.updateToHead(node);
					} else {
						_open.add(node);
					}
				}
			}
		}
	}
}